package medium;

import java.util.ArrayList;
import java.util.List;

/**
 * @author cmqzyd0700@163.com
 * @version 1.0
 * @since 2022/5/2 16:24
 */
public class No89_格雷编码 {
    public static void main(String[] args) {
        Solution89 solution89 = new Solution89();
        List<Integer> list = solution89.grayCode(3);
        System.out.println(list);
    }
}

class Solution89 {
    public List<Integer> grayCode(int n) {
        // 0,元素个数2^n
        //动态规划
        //定义dp[n]为 n传进来时候的格雷码序列,即题解
        List<Integer>[] dp = new ArrayList[n + 1];
        //动态规划初始化
        dp[1] = new ArrayList<>();
        dp[1].add(0);
        dp[1].add(1);
        //开始动态规划
        for (int i = 2; i <= n; i++) {
            //开始处理第i个
            dp[i] = new ArrayList<>();
            //处理前缀1情况
            int pow = (int) Math.pow(2, i - 1);
            //获取上一级
            List<Integer> preList = dp[i - 1];
            //加前缀0
            for (int j = 0; j < preList.size(); j++) {
                dp[i].add(preList.get(j));
            }
            //倒序遍历,加前缀1
            for (int j = preList.size() - 1; j >= 0; j--) {
                dp[i].add(preList.get(j) + pow);
            }
        }
        return dp[n];
    }
}







